21. 小明的顺风车[200分]

题目内容

小明自驾回家，为节省旅途成本，决定在网上挂出顺风车服务，有需要的乘客可自行申请服务，由小明决定谁能搭乘顺风车。请你设计一个程序帮助小明将顺风车利益最大化，并返回最大的顺风车收益。具体细节如下：

• 路线统一采用数值表示，小明的起点为 0，终点为 n。
• 搭乘顺风车的乘客起点和终点必须在 0 到 n 之间，且终点值大于起点值。
• 由于小明有家人同行，同一时间段只有一个乘客可以搭乘顺风车。
• 终点数值和起点数值差得到的是乘车距离，单位为公里；每公里顺风车小明收费 1 元。

输入描述

• n：整数，表示小明的终点位置，1 < n < 1000
• passengers：乘客申请列表，每个乘客由 [起点, 终点] 组成，乘客数量不超过 300

输出描述

输出小明该趟顺风车的最大收益（最大总乘车距离）。

样例

样例 1

输入

10
0,3 1,4 3,8 5,10

输出

8

说明：

• 乘客 1：[0, 3]，距离 3 公里，收益 3 元
• 乘客 2：[1, 4]，距离 3 公里，收益 3 元
• 乘客 3：[3, 8]，距离 5 公里，收益 5 元
• 乘客 4：[5, 10]，距离 5 公里，收益 5 元

最优选择方案：

• 方案 A：选择乘客 1 和乘客 3，[0, 3] 接载完成后恰好 [3, 8] 开始，总收益 3 + 5 = 8 元
• 方案 B：选择乘客 2 和乘客 4，总收益 3 + 5 = 8 元

最大收益为 8 元。

样例 2

输入

10
0,5 1,2 3,6 5,8 6,10

输出

9

说明：

• 乘客 1：[0, 5]，距离 5 公里
• 乘客 2：[1, 2]，距离 1 公里
• 乘客 3：[3, 6]，距离 3 公里
• 乘客 4：[5, 8]，距离 3 公里
• 乘客 5：[6, 10]，距离 4 公里

最优选择方案：选择乘客 1 [0, 5] 和乘客 5 [6, 10]，总收益 5 + 4 = 9 元。

样例 3

输入

20
0,5 5,10 10,15

输出

15

说明： 三个乘客完全不重叠，可以全部选择，收益 5 + 5 + 5 = 15 元。

代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line', (input) => {
    const n = Number(input);
    rl.on('line', (input) => {
        const passengers = input.split(' ').map((item) => item.split(',').map(Number));
        passengers.sort((a, b) => a[1] - b[1]);
        const dp = Array(passengers.length).fill(0);
        let ans = 0;
        for (let i = 0; i < passengers.length; i++) {
            const [f, l] = passengers[i];
            dp[i] = l - f;
            for (let j = 0; j < i; j++) {
                const [f1, l1] = passengers[j];
                if (l1 <= f) {
                    dp[i] = Math.max(dp[i], dp[j] + l - f);
                }
            }
            ans = Math.max(dp[i], ans);
        }
        console.log(ans);
    });
});